package sword.chapter2Array;

/**
 * 和大于或等于k的最短子数组
 * 同向双指针
 * <p>
 * 输入一个由正整数组成的数组和一个正整数k，请问数组中有多少个数字乘积小于k的连续子数组？
 * 例如输入数组[10, 5, 2, 6]，k的值为100，有8个子数组的所有数字的乘积小于100，
 * 它们分别是[10]、[5]、[2]、[6]、[10, 5]、[5, 2]、[2, 6]和[5, 2, 6]。
 *
 * @author K
 * @date 2021-10-20 22:40
 */
public class S8SumBigK {

    public static void main(String[] args) {
        int[] nums = new int[]{5, 1, 4, 3, 4};
        int k = 7;
        int i = minSubArrayLength(k, nums);
        System.out.println();
        int i1 = minSubArrayLength2(k, nums);
        System.out.println();
    }

    public static int minSubArrayLength(int k, int[] nums) {
        int left = 0;
        int right = 0;
        int minLength = Integer.MAX_VALUE;
        while (right <= nums.length - 1) {
            int sum = 0;
            for (int a = left; a <= right; a++) {
                sum += nums[a];
            }
            if (sum >= k) {
                minLength = Math.min(minLength, right - left + 1);
                left++;
            } else {
                right++;
            }
        }
        return minLength;
    }

    public static int minSubArrayLength2(int k, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= k && left < right) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= nums[left++];
            }
        }
        return minLength;
    }
}
